package swordoffer.offer07;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length == 0 || in.length == 0) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return myBuild(pre, 0, pre.length - 1, map, 0, in.length - 1);
    }

    public TreeNode myBuild(int[] pre, int pLeft, int pRight, Map<Integer, Integer> map, int iLeft, int iRight) {
        if (pLeft > pRight) {
            return null;
        }
        int rootVal = pre[pLeft];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        root.left = myBuild(pre, pLeft + 1, pLeft + rootIndex - iLeft, map, iLeft, rootIndex - 1);
        root.right = myBuild(pre, pLeft + 1 + rootIndex - iLeft, pRight, map, rootIndex + 1, iRight);
        return root;
    }
}
